package com.zhengwl.study.algorithm;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.apache.commons.lang3.ArrayUtils;
import com.google.common.base.Function;
import com.google.common.collect.Lists;

/***
 * question:给出一组非负数，重新排列它们的顺序把他们组成一个最大整数 如：给出 [1, 20, 23, 4,
 * 8]，返回组合最大的整数应为8423201
 * 
 * @author wlzheng
 *
 */
public class LargestNumber {
	public String getLargestNumber(int[] num) {
		List<String> items = Lists.transform(Arrays.asList(ArrayUtils.toObject(num)), new Function<Integer, String>() {
			@Override
			public String apply(Integer input) {
				return input.toString();
			}
		});
		Collections.sort(items, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				String lrStr = o1 + o2;
				String rlStr = o2 + o1;
				return lrStr.compareTo(rlStr);
			}
		});

		String result = "";
		for (int i = items.size() - 1; i >= 0; i--) {
			result += items.get(i);
		}
		int i = 0;
		while (i < result.length() && result.charAt(i) == '0')
			i++;
		if (i == result.length())
			return "0";
		return result.substring(i);
	}

	/**
	 * @param num:
	 *            A list of non negative integers
	 * @return: A string
	 */
	public String getLargestNumber2(int[] num) {
		String result = "";
		quickSort(num, 0, num.length - 1);
		for (int i = 0; i < num.length; i++)
			result += num[i];
		// 去除左边无效的 0
		int i = 0;
		while (i < result.length() && result.charAt(i) == '0')
			i++;
		if (i == result.length())
			return "0";
		return result.substring(i);
	}

	// 可以理解为逆序排序，排序后直接链接起来就是答案
	public void quickSort(int[] num, int low, int high) {
		if (low > high)
			return;
		int i = low;
		int j = high;
		int x = num[i];
		while (i < j) {
			while (i < j && compare(x, num[j]))
				j--;
			if (i < j) {
				num[i] = num[j];
				i++;
			}
			while (i < j && compare(num[i], x))
				i++;
			if (i < j) {
				num[j] = num[i];
				j--;
			}
		}
		num[i] = x;
		quickSort(num, low, i - 1);
		quickSort(num, i + 1, high);
	}

	// AB > BA 说明A应该在前面，B应该在后面
	public boolean compare(int A, int B) {
		String left = A + "";
		String right = B + "";
		String leftright = left + right;
		String rightleft = right + left;
		return leftright.compareTo(rightleft) > 0;
	}

}
